package Hot_100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

// 集合是无序的，所以集合里的元素顺序无所谓
public class T90_subsetsWithDup {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);      //先对数组进行排序
        if (nums.length == 0) {
            return result;
        }
        search(nums, 0);
        return result;
    }

    public void search(int[] nums, int index) {
        result.add(new ArrayList<>(path));
        for (int i = index; i < nums.length; i++) {
            if (i > index && nums[i] == nums[i - 1]) {
                //不同分支上不应该出现相同的元素（先将nums数组排序，这样相同元素就是相邻的），否则会出现重复解（相同分支上可以出现）
                //而相同分支上是允许出现重复元素的
                continue;
            }
            path.add(nums[i]);                   //选
            search(nums, i+1);
            path.remove(path.size() - 1);  //不选,不会进入下一层递归,只会进入下一轮循环,这样就不会计算重复解
//          search(nums, tmp);  回溯直接进入下一轮,不用再递归下去了
        }
    }
}
